// Copyright [2022] <Tianyu Zhu, Shizhen Zhao, Zihang Ren>

#ifndef DOUBLE_PULSE_H_
#define DOUBLE_PULSE_H_

#include <functional>
#include <queue>
#include <unordered_map>
#include <vector>

#include "algorithm.h"
#include "graph.h"

class DoublePulse : public Algorithm {
 public:
    DoublePulse() {}
    ~DoublePulse();
    void SetupTopology(Graph* graph) override;
    Path FindPath(const Flow& flow) override;
    void print() const;

 private:
    template <class T>
    struct Node {
        Node(T id_in, int distance_in)
            : id(id_in), distance(distance_in) {}

        friend bool operator<(const Node<T> &a, const Node<T> &b) {
            return a.distance > b.distance;
        }
        T id;
        int distance;
    };

    struct PulseInfo {
        PulseInfo() {}
        void Clear() {
            src_delay_to_cost_map.clear();
            dst_delay_to_cost_map.clear();
        }
        std::unordered_map<int, int> src_delay_to_cost_map;
        std::unordered_map<int, int> dst_delay_to_cost_map;
    };

    // Helper functions
    void DstDijkstra(NodeId dst_node, bool flag, int* node_to_dst_dis);
    void SrcDijkstra(NodeId src_node, bool flag, int* node_to_src_dis);
    void Dfs();
    bool updateSrcPath(NodeId u, int cost, int delay);
    bool updateDstPath(NodeId u, int cost, int delay);
    std::vector<Link*> GetOrderedEgressLinks(NodeId node, int delay);
    std::vector<Link*> GetOrderedIngressLinks(NodeId node, int delay);


    // Variables for initialization
    int* dst_cost_map_;
    int* dst_delay_map_;
    int* src_cost_map_;
    int* src_delay_map_;
    int num_nodes_;

    // Variables for pulse search
    bool* src_visited_;
    bool* dst_visited_;
    PulseInfo* info_;
    Flow flow_;
    int total_cost_;
    Path results_;
};

#endif  // DOUBLE_PULSE_H_